#include <iostream>
#include <vector>
#include <algorithm>
#include <sys/time.h>

using namespace std;

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode *buildTree(vector<int> &preorder,int preL,int preR, vector<int> &inorder, int inL,int inR)
{
  if((preR-preL) <= 0||(inR-inL)<=0)
    return NULL;

  int len = preR - preL;


  struct TreeNode *root =new TreeNode(0);
  root->val = preorder[0];
  if(len==0)
  {
    root->left = NULL;
    root->right = NULL;
    return root;
  }

  int index=inL;
  while(preorder[preL]!=inorder[index])
  {
    index++;
  }

  //preL++;
  //preR = preL + (index - inL);
  //left Tree
  root->left = buildTree(preorder,preL+1,preL+index-inL,inorder,inL,index-1);

  root->right = buildTree(preorder,preR-(inR-index)+1,preR,inorder,inR-(inR-index-1),inR);






  return root;
}



TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) 
{

  TreeNode * n=NULL;
  if(preorder.size()==0)
    return n;
  n =  new TreeNode(0);
  n->val=preorder[0];

  if(preorder.size()==1)
  {
    /*    cout<<"porder:"<<preorder[0]<<endl;*/
    //cout<<"inorder:"<<inorder[0]<<endl;
    /*cout<<"---------------"<<endl;*/
    n->right= NULL;
    n->left = NULL;
    return n;
  }

  /*  cout<<"preorder"<<endl;*/
  //for(auto iter = preorder.begin();iter!=preorder.end();++iter)
  //{
  //cout<<*iter<<",";
  //}
  //cout<<endl;

  //cout<<"inorder"<<endl;
  //for(auto iter = inorder.begin();iter!=inorder.end();++iter)
  //{
  //cout<<*iter<<",";
  //}
  //cout<<endl;
  /*cout<<"-----------------"<<endl;*/

  std::vector<int>::iterator first = std::find(inorder.begin(), inorder.end(), preorder[0]);
  vector<int> lTreeInOrder;
  vector<int> rTreeInOrder;
  std::copy(inorder.begin(), first, std::back_inserter(lTreeInOrder));
  std::copy(first+1, inorder.end(), std::back_inserter(rTreeInOrder));
  int lenLTree= lTreeInOrder.size();

  inorder.clear();
  inorder.shrink_to_fit();

  vector<int> lTreePrOrder;
  vector<int> rTreePrOrder;
  std::copy(preorder.begin()+1, preorder.begin()+lenLTree+1, std::back_inserter(lTreePrOrder));
  std::copy(preorder.begin()+lenLTree+1, preorder.end(), std::back_inserter(rTreePrOrder));  

  preorder.clear();
  preorder.shrink_to_fit();

  n->left = buildTree(lTreePrOrder,lTreeInOrder);
  n->right = buildTree(rTreePrOrder,rTreeInOrder); 

  return n;


}

void preDFS(TreeNode *t)
{
  if(t!=NULL)
  {
    cout<<t->val<<",";

    preDFS(t->left);

    preDFS(t->right);
  }
  return ;

}

int main(int argc,char *argv[])
{

  vector<int> pr={1,2,3,4,5,7,6};
  vector<int> in={3,2,5,7,4,6,1};

  struct  timeval    tv1,tv2;
  struct  timezone   tz;
  int time1 = gettimeofday(&tv1,&tz);

  //func();
  TreeNode *t=buildTree(pr,in);

  int time2 = gettimeofday(&tv2,&tz);

  cout << "time consuming:" << tv2.tv_usec - tv1.tv_usec <<"us"<< endl;
  preDFS(t);



  return 0;
}
